package cn.edu.bjut.my.thinkinjava._20200427_slideWindow;

import java.util.Arrays;
import java.util.HashMap;

/**
 * 目的：本例用来巩固滑动窗口练习
 *
 * 题目：给定S1、S2，写一个函数判断S2是否包含S1的排列
 * 例：S1="ab" S2="eidbaooo" 输出 True
 *
 * 思路1：求取S1的全排列，判断S2.contains
 * 全排列是个递归问题，留在下一节介绍
 * 思路2：一般子串问题、链表问题会用到双指针；且子串问题使用滑动窗口
 * 滑动窗口问题
 * 1：t成hashmap,使用need记录 t所需字符的种类和数量
 * 声明一个window的hashmap，记录窗口内
 * 声明valid记录 need与window 相同种类数
 * 2：双指针 right++
 * 2.1当s.getChar(right)是need中的元素时，window.put(s.getChar(right)).value++
 * 2.2当window.get(s.getChar(right))==need.get(s.getchar(right)),valid++
 * 2.3 valid==need的size时，
 * 2.3.1 如果s.getChar(left)在need中存在，
 * 2.3.1.1 记录此事字符串 start、length left++
 * 2.3.1.2 如果need.get().value==window.get().value,valid--
 * 2.3.2 widow.get().value--
 * 2.4 返回
 */
public class CheckInclusion {
    public boolean checkInclusion(String t, String s) {
        HashMap<Character, Integer> need = new HashMap<>();
        HashMap<Character, Integer> window = new HashMap<>();

        for (char c : t.toCharArray()) {
            need.put(c, need.get(c) == null ? 1 : need.get(c) + 1);
        }

        int left = 0, right = 0;
        int valid = 0;
        while (right < s.length()) {
            char c = s.charAt(right);
            right++;
            if (need.get(c) != null) {
                window.put(c, window.get(c) == null ? 1 : window.get(c) + 1);
                if (window.get(c) == need.get(c)) {
                    valid++;
                }
            }
            while (right - left >= t.length()) {
                if (valid == need.size()) {
                    return true;
                }

                char d = s.charAt(left);
                left++;
                if (need.get(d) != null) {
                    if (window.get(d) == need.get(d)) {
                        valid--;
                    }
                    window.put(d, window.get(d) - 1);
                }
            }

        }
        return false;
    }

    public static void main(String[] args) {
        CheckInclusion checkInclusion = new CheckInclusion();
        String s = "eidbaooo";
        String t = "eo";
        boolean b = checkInclusion.checkInclusion(t, s);
        System.out.println(b);
    }


}
